//
//  234_回文链表.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/8.
/**
 234. 回文链表
 https://leetcode.cn/problems/palindrome-linked-list/description/
 链表是对称的
 */

import UIKit

class HuiWenList: NSObject {
    
    func QA() {
        var link =  LinkedList<Int>()
        let head = link.creatList(array: [1,2,3,4,2,1])
        let result = isPalindrome(head)
        print(result)
    }
    
    
    func isPalindrome(_ head: ListNode<Int>?) -> Bool {
        if head?.next == nil {
            return true
        }
        if head?.next?.next == nil {
            return head?.val == head?.next?.val
        }
        var head = head
        let midNode = middleNode(&head)
        var next = midNode?.next
        var rHead = revertNode(&next)
        var lHead = head
        while let temp = rHead {
            if temp.val != lHead?.val {
                return false
            }
            lHead = lHead?.next
            rHead = rHead?.next
        }
        return true
    }
    
    /// 找到中间节点
    /// - Parameter head: 头结点
    /// - Returns: 结果
    func middleNode(_ head: inout ListNode<Int>?) -> ListNode<Int>? {
        var slow = head
        var fast = head
        while fast?.next != nil && fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
    
    /// 翻转链表
    /// - Parameter head: 头结点
    /// - Returns: 返回节点
    func revertNode(_ head: inout ListNode<Int>?) -> ListNode<Int>? {
        var newHead: ListNode<Int>? = nil
        while head != nil{
            let node = head?.next
            head?.next = newHead
            newHead = head
            head = node
        }
        return newHead
    }
}
